package test;
//初始化两个链表
class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class 合并两个有序链表 {
    public static void main(String[] args) {
        // 初始化链表1
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(2);
        l1.next.next = new ListNode(4);

        // 初始化链表2
        ListNode l2 = new ListNode(1);
        l2.next = new ListNode(3);
        l2.next.next = new ListNode(4);

        // 合并两个有序链表
        ListNode merged = mergeTwoLists(l1, l2);

        // 打印合并后的链表
        while (merged != null) {
            System.out.print(merged.val + " ");
            merged = merged.next;
        }
    }
/*
mergeTwoLists函数实现了将两个有序链表合并的功能，
其实现思路为递归。如果其中一个链表为空，则直接返回另一个链表；
否则比较两个链表头节点的值，将较小的节点作为合并后链表的头节点，
然后将原链表中的头节点指向剩下的节点和另一个链表的合并结果。如此递归下去，
直到其中一个链表为空为止。最后返回合并后的链表。
 */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
